package com.qqn.zcy.class02;

public class Code02_EvenTimesOddTimes {
    /**
     * 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
     */
    // arr 中，只有一种数，出现奇数次
    public static void printOddTimesNum1(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        System.out.println(eor);
    }

    // 怎么把一个 int 类型的数 提取出最右侧的 1 来
    // eor最右侧的1，提取出来
    // eor :          00110010110111000  取反+1就是自己的相反数 ~eor+1 = -eor
    // ~eor:          11001101001000111
    // ~eor+1:        11001101001001000
    // eor&(~eor+1):  00000000000001000
    // rightOne :     00000000000001000

    /**
     * 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
     *
     * @param arr
     */
    public static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) { // [a,a,a,b,c,c,d,d,e,e,e,e]
            eor ^= arr[i]; // 最终 eor = a ^ b
        }
        // a 和 b是两种数
        // eor != 0
        // 将 eor最右侧的1，提取出来
        // eor :          00110010110111000  取反+1就是自己的相反数 ~eor+1 = -eor
        // ~eor:          11001101001000111
        // ~eor+1:        11001101001001000
        // eor&(~eor+1):  00000000000001000
        /**
         * 因为 eor是a和b异或的结果 所以他们最右的 1 肯定不是相同的位置  0010 ^ 0100 = 0110
         * 所以提取出最右的 1 只能去找到 a 或者 b 中的一个
         */
        int rightOne = eor & (-eor); // 提取出最右的1
        // rightOne :     00000000000001000

        int onlyOne = 0; // eor`
        for (int i = 0; i < arr.length; i++) {
            // arr[1]   = 111100011110000
            // rightOne = 000000000010000
            if ((arr[i] & rightOne) != 0) {
                /**
                 * 异或完偶数个数的数直接消掉了就剩最右侧1与rightOne位置相同的数了
                 * 这样就拿到了  a ^ b 中的其中一个
                 */
                onlyOne ^= arr[i];
            }
        }
        System.out.println("其中一个是：" + onlyOne + "  另外一个是： " + (onlyOne ^ eor)); // a ^ a ^ b = b  拿到另外一个
    }

    public static void main(String[] args) {
        int a = 5;
        int b = 7;

        a = a ^ b;
        b = a ^ b;
        a = a ^ b;

        System.out.println(a);
        System.out.println(b);

        int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
        printOddTimesNum1(arr1);

        int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
        printOddTimesNum2(arr2);

    }
}
